package com.LeeCode;

/**
 * 反转偶数长度组的节点
 */

public class Code2074 {
    public static void main(String[] args) {
        int[] arr = {1, 1, 0, 6, 5};
        ListNode head = Utils.arrayToListNode(arr);
        Utils.printListNode(new Code2074().reverseEvenLengthGroups(head));
    }

    public ListNode reverseEvenLengthGroups(ListNode head) {
        //先计算得到链表长度
        int n = 0;
        for (ListNode cur = head; cur != null; cur = cur.next) n++;
        int k = 0, s = 0;
        ListNode dummy = new ListNode(0, head);
        ListNode p0 = dummy, pre = dummy, cur = head;
        while (cur != null && s <= n) {
            //计算出每组能分得的长度
            int len = n - s < ++k ? n - s : k;
            s += k;
            if (len % 2 == 0) {
                //内部翻转
                for (int i = 0; i < len && cur != null; i++) {
                    ListNode next = cur.next;
                    cur.next = pre;
                    pre = cur;
                    cur = next;
                }
                //外部翻转
                ListNode p1 = p0.next;
                p1.next = cur;
                p0.next = pre;
                p0 = p1;
                pre = p1;
            } else {
                for (int i = 0; i < len && cur != null; i++) {
                    pre = cur;
                    cur = cur.next;
                }
                p0 = pre;
            }
        }
        return dummy.next;
    }
}
